//图
#include <stdio.h>
#include <stdlib.h>
#define maxSize 999
int main(int argc, char *argv[]) {
	/**图的基本概念**/
	/*
		图————由结点（顶点）和边（用两顶点的序偶表示）组成————若两结点之间，有边相连，则称 两结点相邻
		
		有向图————每条边 都有方向————通常将有向图的边 称为“弧”————有箭头的一端叫“弧头”，没箭头的一端叫“弧尾”，记为：< V头，V尾 >
			 ————顶点V的入度 == 指向V的 弧的条数 ； 顶点V的出度 == 从V出发的 弧的条数
		完全有向图————有向图 若有 n个结点，则最多有n(n-1)个边————>此时称为“完全有向图”
	
		无向图————每条边 都没有方向————边 记为：（ V1，V2 ）== < V头，V尾 > + < V尾，V头 >
			 ———— 顶点V的度 == 连接V的 边的条数
		完全无向图————无向图 若有 n个结点，则最多有n(n-1)/2个边————>此时称为“完全无向图”
	
		路径————为相邻顶点的 序偶所构成的 序列表示
		路径长度————路上，边的数目
		简单路径————序列中，顶点 不重复出现的 路径
		回路————在一条路径中，第一个顶点和最后一个顶点 相同
																						极大：不能再添加 顶点了
		在无向图中————顶点V1到顶点V2有路径，则称V1与V2连通————所有顶点都连通，该图为 连通图————否则，该图的极大连通子图，为连通分量
		
		在有向图中————顶点V1到顶点V2有路径，则称从V1到V2连通————所有顶点都连通，该图为 强连通图————否则，该图的极大强连通子图，为强连通分量
	
		图中，每条边都可附一个对应的数————与边相关，称为权————表示一个点到另一个点 所花费的代价
		网————也称“带权图”，边上带有权的图
	*/
}

/*** 图的存储结构 ***/
/*
邻接矩阵————表示顶点之间 有相邻关系的矩阵————图的顺序存储结构
	G=(V,E)是具有 n个顶点的图，顶点序号为 0，1，……，n-1
	
	定义n阶方阵A 为G的邻接矩阵，其具有如下性质：
		1、A[i][j]=1,表示顶点i,j之间 有边——邻接
		2、A[i][j]=0,表示顶点i,j之间 无边——不邻接
		3、记：A[i][i] = 0
		4、当然，不止可以赋0、1， 还可以赋值 权
	
	邻接矩阵————顺序存储结构，阶数即为 图的顶点数
	无向图的邻接矩阵————对称————其中 1的个数==边的个数*2————顶点i的度 == 第i行/列 的数字和
	有向图的邻接矩阵————其中 1的个数==边的个数————顶点i的出度 == 第i行 的数字和————顶点i的入度 == 第i列 的数字和
*/
typedef struct{
	int NO;//存储顶点编号
	char data;//顶点的数据
	
}Vertex;//顶点结构————存储各结点信息

typedef struct{
	float edges[maxSize][maxSize];//定义邻接矩阵，存储 权值————表示各结点关系
	int note,edge;//表示 顶点数，边数
	
	Vertex vex[maxSize];//存放顶点信息
}MatrixGraph;//用邻接矩阵 表示图


/*
邻接表————图的链式存储结构
	对图的每一个结点i，都建立一个单链表（邻接表）——>第一个结点：存放 结点信息，指向第一个边结点————>（顶点表）（顶点结点）
										 ——>其余结点：存放 涉及该结点的 边的信息（即：相邻结点的序号），指向下一个边结点————>（边表）
																						————每一个边，都会被两个 边结点表示
*/
typedef struct edgeNode{
	int adjacentNode;//相邻结点的序号
	struct edgeNode *nextEdge;//指向下一个边结点
}edgeNode;//边结点

typedef struct vertexNode{
	char data;//顶点信息
	edgeNode *nextEdge;//指向下一个边结点
}vertexNode;//顶点 结点

typedef struct {
	vertexNode adjacentList[maxSize];//创造一系列 邻接表————存储 所有结点信息
	int node,edge;//结点个数、边的个数
}Adjacentgraph;//用邻接表 表示图

/*
邻接多重表————也由 顶点表、边表 构成
		顶点表————存储顶点信息、指向下一个边结点
		边表结点————标记域（用来标记该边 是否被遍历过）、（2个域）存储该边 连接的两个顶点的 序号、（2个域）分别指向 两端结点的 下一个边结点
	
	效果：
		1、依附于同一顶点的边————在一个链表中
		2、边数 == 边表结点个数————避免了空间的浪费
*/
		

/*** 图的遍历算法操作 ***/
//针对连通图的 DFS、BFS
/*
图的深度优先搜索遍历（DFS）：
				1、访问出发顶点v1，并标记已访问
				2、访问v1的相邻顶点 v2————访问v2的相邻结点v3————依次进行，直到没有未被访问过的 邻接结点，假设到了vj
				3、退回v(j-1)，访问其另一个相邻顶点（未被访问）———— 继续步骤2
				4、步骤2、3循环，即可遍历 图中所有顶点
*/
//假设 图以邻接表为存储结构————其DFS遍历算法如下：
int visit[maxSize];//标记 结点是否被访问————结点的序号对应 元素的索引————全部元素初始为 0，被访问则为1
void DFS(Adjacentgraph *G,int v)//引入邻接表图、出发顶点的序号
{
	edgeNode *p;//指向边结点的指针
	
	visit[v] = 1;
	printf("%d",v);//表示已访问 该序号的结点
	
	p = G->adjacentList[v].nextEdge;//p指向 v结点的第一条边
	while(p!=NULL)//当边存在，邻接结点就存在————就试着访问它
	{
		if(visit[p->adjacentNode]==0)//若相邻结点未访问
			DFS(G,p->adjacentNode);//递归访问
		
		p = p->nextEdge;//当该分支上 没有未被访问过的 邻接结点，则换一个分支
	}
}

/*
图的广度优先搜索遍历（BFS）：
		基本思想：
			1、访问出发顶点v1，标记访问
			2、然后访问v1 邻接的全部顶点a1,a2,a3……，标记访问
			3、再依次范围 a1,a2,a3 的全部邻接顶点
			4、循环2、3，直到完全访问完毕
		
		队列实现：
			1、访问出发顶点v1，标记访问————将其入队
			2、让 某顶点 出队的同时，让该顶点 的全部 未被访问的 相邻顶点入队
			3、直到队列为空时————遍历完毕
*/
void BFS(Adjacentgraph *G,int v,int visit[maxSize])//引入邻接表图、出发顶点的序号、用于标记的数组
{
	edgeNode *p;//指向边结点的指针————用来访问 所有邻接结点
	int queue[maxSize],front=0,rear=0;//定义一个队列
	
	int j;//用于记录出队的顶点 序号
	visit[v] = 1;
	printf("%d",v);//表示已访问 该序号的结点
	
	rear=(rear+1)%maxSize;
	queue[rear]=v;//结点序号的 入队操作
	
	while(front!=rear)//队不为空时
	{
		front=(front+1)%maxSize;//顶点出队
		j = queue[front];//记录出队的顶点————之后让其所有 未访问的 相邻结点 入队,代码实现如下：
		p = G->adjacentList[j].nextEdge;
		while(p!=NULL)
		{
			if(visit[p->adjacentNode]==0)//未访问过
			{
				visit[p->adjacentNode] = 1;
				printf("%d",p->adjacentNode);//访问
				//入队
				rear=(rear+1)%maxSize;
				queue[rear]=p->adjacentNode;
			}
			p=p->nextEdge;
		}
	}
}

//针对 非连通图的 dfs、bfs————利用循环（遍历 各个极大连通子图）
//深度优先搜索遍历
void dfs(Adjacentgraph *g)
{
	for(int i=0;i<g->node;i++)
	{
		if(visit[i]==0)
			DFS(g,i);
	}
}
//广度优先搜索遍历
void bfs(Adjacentgraph *g)
{
	for(int i=0;i<g->node;i++)
		{
			if(visit[i]==0)
				BFS(g,i,visit);
		}
}


/*** 最小（代价）生成树 ***/
/*
普里姆算法：图————>构造 最小生成树
	1、从图中选一个顶点————让图中所有的边，均变成 虚线
	2、在 该顶点相邻的 边中，选择一个权最小的，变成实线
*/